Paths, Contours, and Glyphs
In the field of computer graphics, two-dimensional paths are often used to represent shapes of graphical objects that require rendering to a physical device. Examples of such objects include glyphs, structured vector graphics, illustrations, corporate logos, maps, and the like. Although we focus here on digital type, possibly the most common and important two-dimensional object, the following description applies to all types of two-dimensional objects. A collection of glyphs with a consistent design is called a font. Fonts are ubiquitous in computer applications. Fonts can be rendered on many types of physical devices such as computer monitors, telephones, printers, cameras, personal digital assistants (PDAs), global positioning devices, televisions, and the like.
A glyph is described by a path. Formally, a path includes a set of contours and a fill rule. A contour is a bounded and closed region represented as a sequence of piece wise continuous directed segments. Segments can be linear or curved. Fill rules include a nonzero winding rule and an even-odd parity rule.
The even odd parity rule determines the “insideness” of a point for a shape defined by a path by drawing a ray from that point to infinity in any direction and counting the number of path segments from the shape that the ray crosses. If this number is odd, then the point is inside; if even, the point is outside.
The non-zero winding rule is more complex. For a given path C and a given point construct a ray, i.e., a straight line, heading out from P in any direction towards infinity. Find all the intersections of C with this ray. Score up the winding number as follows: for every clockwise intersection, i.e., the path passing through the ray from left to right, as viewed from P, subtract 1; for every counter-clockwise intersection, i.e., path passing from right to left, as viewed from P, add 1. If the total winding number is zero, then P is outside C; otherwise, P is inside C.
Glyphs for computer applications are most frequently designed according to the nonzero winding rule. Glyphs can be filled with, e.g., a solid color, or their paths can be outlined, without filling interior portions, to achieve various visual effects.
Nonzero Winding Rule
There are several problems when rendering paths that are to be filled or outlined according to the nonzero winding rule. First, many rendering systems do not support the nonzero winding rule because of its complexity, whereas almost all rendering systems support the even-odd parity rule. Second, the nonzero winding rule is slower to execute than the even-odd parity rule. This can be a problem when rendering, on resource constrained devices.
Third, as shown in FIGS. 6A, 6B, and 6C for partial glyphs, the nonzero winding rule can produce “interior edge haloes” 601-603 for rendering systems that operate in a certain way. The halo artifacts occur because the rendering first fills the shape, and then unconditionally antialiases all the edges, which spoils the filling.
Other interior artifacts are shown in FIGS. 6D and 6E. FIG. 6D shows a path 611 with two (directed) contours that would be outlined correctly in the prior art as the letter Q 612. However, if the path 621 is defined by three contours or natural “strokes” as shown in FIG. 6E, then the interior (non-boundary) edges are not removed during the rendering, and the outline 622 is incorrect.
Other problems exist when using the nonzero winding rule, even for rendering systems that support the rule. Paths can often contain self-intersections, coincident segments, and other degenerate cases that rendering systems improperly handle because the systems incorrectly fills or outlines the path.
Therefore, it is desirable to convert a path defined by the nonzero winding rule to an equivalent path that can be rendered with either the even-odd parity rule or the nonzero winding rule. It would be ideal if the equivalent path was simpler, smaller, faster to render, and did not exhibit any incorrect regions or annoying rendering artifacts due to degenerate cases such as those described above.
Furthermore, it is desirable to enable the correct and accurate determination of a segment of a path as either interior or exterior, even when the path contains self-intersections, coincident segments, and other degenerate cases. The correct and accurate determination for the segment permits path rendering systems, path compression systems, path simplification systems, and the like to function correctly when the path contains degenerate cases.
U.S. Pat. No. 6,111,587 describes a method that converts a polygon defined by a nonzero winding rule to a polygon defined by an even-odd parity rule. That method operates on closed polygons with linear edges, where each polygon includes a set of labeled contours. The method does not correctly handle degenerate cases such as coincident segments, coincident points, and self-intersections in all of their variations. That method cannot render a simplified polygon defined by the nonzero winding rule as output.
U.S. Pat. No. 7,321,373 describes a method for performing set operations on two or more arbitrary paths to produce a simple outline path. Like U.S. Pat. No. 6,111,587, that method does not handle all degenerate cases correctly.